import java.util.Stack;

public class No027 {
    /**
     * 操作给定的二叉树，将其变换为源二叉树的镜像
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        Mirror(root.left);
        Mirror(root.right);
    }

    public void Mirror1(TreeNode root) {

        // 空树
        if (root == null) return;
        // 左右均为空
        if (root.left == null && root.right == null) return;
        // 用来遍历的栈
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        TreeNode curNode;
        TreeNode tempNode;

        // 深度优先
        while (!stack.isEmpty()) {
            curNode = stack.pop();
            if (curNode == null) continue;
            if (curNode.left == null && curNode.right == null) continue;
            // 交换
            tempNode = curNode.left;
            curNode.left = curNode.right;
            curNode.right = tempNode;
            stack.push(curNode.left);
            stack.push(curNode.right);
        }
    }
}
